package demo.kk;


/**
 * @author : feixiang.li
 * @since : 2025-09-16 17:41
 */
public class 快速排序 {

    public static void main(String[] args) {
        int[] a = {5, 4, 3, 2, 1};
        快速排序 快速排序 = new 快速排序();
        快速排序.quickSort(a, 0, a.length - 1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    public void quickSort(int[] a, int low, int high) {
        if (low < high) {
            int pivot = partition(a, low, high);
            quickSort(a, low, pivot - 1);
            quickSort(a, pivot + 1, high);
        }
    }

    public int partition(int[] a, int low, int high) {
        // 获取第一个元素作为轴点元素
        int key = a[low];
        int hole = low;
        while (low < high) {
            // 从后往前找比轴点元素小的元素
            while (low < high && a[high] >= key) {
                high--;
            }
            // 交换轴点元素和找到的元素
            a[hole] = a[high];
            hole = high;

            // 从前往后找比轴点元素大的元素
            while (low < high && a[low] <= key) {
                low++;
            }
            a[hole] = a[low];
            hole = low;
        }
        a[hole] = key;
        return hole;
    }
}
